#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

struct MatchingBlock{
    int ubeg;
    int vbeg;
    int len;
};

class EditDistance{
    public:
        static float levenstein(const vector<int> &u, const vector<int> &v, int modCost = 1);
        static float partialRatio(const vector<int> &u, const vector<int> &v);
        static float tokenSetRatio(vector<int> u, vector<int> v);
        static float jaroWinkler(const vector<int> &u, const vector<int> &v);
        static float partialSortRatio(vector<int> u, vector<int> v);
        static float sortRatio(vector<int> u, vector<int> v);
        static float wordMatch(vector<int> u, vector<int> v, const std::vector<bool> &stop_words, const std::vector<float> &weight);

    private:
        static int* computeDistance(const vector<int> &u, const vector<int> &v, int modCost);
        inline static int accessDistance(int* dis, int sz, int i, int j);
        static vector<MatchingBlock> buildMatchingBlocks(const vector<int> &u, const vector<int> &v, int *dis, int modCost);
        static vector<int> subVector(const vector<int> &v, int start, int end);
        static void removeSortRepeat(vector<int> &u);
        static float getWeight(const vector<float> &weight, const int key, const vector<bool> &stop_words);
};
